package com.yeung.swordoffer;

/**
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
 * 另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
 * （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 */
public class 复杂链表的复制 {
    public static void main(String[] args) {

    }

    public RandomListNode Clone(RandomListNode pHead) {
        //先复制节点,复制的节点作为原节点的兄弟节点
        //如A-copyA-B-copyB

        if (pHead == null) return null;
        RandomListNode walkNode = pHead;
        while (walkNode != null) {
            RandomListNode clone = new RandomListNode(walkNode.label);
            //链接为兄弟节点
            clone.next = walkNode.next;
            walkNode.next = clone;
            walkNode = clone.next;
        }
        //然后复制随机节点
        //        为新copy结点的random域指定值
        initRandom(pHead);
        return splitTable(pHead);
    }

    void initRandom(RandomListNode pHead) {
        RandomListNode walkNode = pHead;
        RandomListNode cWalkNode = pHead;
        while (walkNode != null) {
            cWalkNode = walkNode.next;
            if (walkNode.random != null) {
                cWalkNode.random = walkNode.random.next;
            }
            walkNode = cWalkNode.next;
        }

    }

    //    将链表和其copy版本分为两个链表
    RandomListNode splitTable(RandomListNode pHead) {
        RandomListNode cpHead = pHead.next;
        RandomListNode walkNode = pHead;
        RandomListNode cwalkNode = cpHead;
        while (walkNode != null) {
            //分开兄弟节点,a->ca->b->cb  |   a->b ,  ca->cb
            walkNode.next = cwalkNode.next;
            walkNode = walkNode.next;
            if (walkNode == null) {
                //到链表尾部了
                cwalkNode.next = null;
            } else {
                cwalkNode.next = walkNode.next;
                cwalkNode = cwalkNode.next;
            }
        }
        return cpHead;
    }

    RandomListNode search(RandomListNode root, int label) {
        while (root != null) {
            if (root.label == label)
                break;
            root = root.next;
        }
        return root;
    }
}
